package com.java.simple.sort;

import java.util.Arrays;

/**
 * @author zhoujunlin
 * @date 2022年08月09日 13:20
 * @desc 快速排序
 * 时间复杂度 nlogn
 * https://blog.csdn.net/weixin_43586713/article/details/119820797
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] numArr = new int[]{1, 10, 2, 8, 3, 4, 7, 6, 5, 9};
        quickSort(numArr, 0, numArr.length - 1);
        System.out.println(Arrays.toString(numArr));
    }

    private static void quickSort(int[] numArr, int start, int end) {
        if (start > end) {
            return;
        }
        // 初始基准数  以最左边数为基准
        int base = numArr[start];
        // 行走的哨兵i,j
        int i = start;
        int j = end;
        while (i < j) {
            while (i < j && numArr[j] >= base) {
                // 当基准右边的数 大于基准数时j-- 否则退出while
                j--;
            }
            while (i < j && numArr[i] <= base) {
                // 当基准左边的数 小于基准数时i++ 否则退出while
                i++;
            }
            // 走到这里说明 右边发现比基准小的数  左边发现比基准大的数
            // 交换之后继续循环
            SwapUtil.swap(numArr, i, j);
        }
        // 走到这里 说明 i=j 即左右i,j重合了
        // 这时候需要将基准数交换  即将基准数交换到重合位置
        SwapUtil.swap(numArr, start, i);
        // 至此  基准左边的数都比基准小  右边的书都比基准大  但是基准左右的序列都是无序的
        // 需要递归快排左右序列
        quickSort(numArr, start, i - 1);
        quickSort(numArr, i + 1, end);
    }


}
